

//给定一棵二叉树 root，返回所有重复的子树。 
//
// 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 
//
// 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [1,2,3,4,null,2,4,null,null,4]
//输出：[[2,4],[4]] 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [2,1,1]
//输出：[[1]] 
//
// 示例 3： 
//
// 
//
// 
//输入：root = [2,2,2,3,null,3,null]
//输出：[[2,3],[3]] 
//
// 
//
// 提示： 
//
// 
// 树中的结点数在[1,10^4]范围内。 
// -200 <= Node.val <= 200 
// 
// Related Topics 树 深度优先搜索 哈希表 二叉树 
// 👍 382 👎 0


import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 652.寻找重复的子树.find-duplicate-subtrees
 *
 * @author orz
 * @since 2022-03-27 17:40:33
 **/

class Solution_652 {
    public static void main(String[] args) {
        Solution solution = new Solution_652().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {

        //记录所有子树以及出现的次数
        private Map<String, Integer> memo = new HashMap<String, Integer>();
        // 记录重复的子树根节点
        private LinkedList<TreeNode> res = new LinkedList<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            traverse(root);
            return res;
        }

        private String traverse(TreeNode root) {
            if (root == null) {
                return "#";
            }

            String left = traverse(root.left);
            String right = traverse(root.right);

            String subTree = left + "," + right + "," + root.val;

            Integer frequency = this.memo.getOrDefault(subTree, 0);
            //重复多次也只会记录一次，所以这里判断的是一次的时候给添加，其他时候都不添加了。
            if (frequency == 1) {
                res.add(root);
            }
            memo.put(subTree, frequency + 1);
            return subTree;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}